package com.leetcode.No0878;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 第 N 个神奇数字
 * @author: Wang Zhihua
 * @date: 2022-11-25
 */
public class Solution {

    private int mod = 1000000007;

    public int nthMagicalNumber(int n, int a, int b) {
        if (a == b) {
            return calMulti(n, a);
        }
        int minCommonMultiple = calMinCommonMultiple(a, b);
        int circleSize = calCircleSize(minCommonMultiple, a, b);
        int circleNum = n / circleSize;
        int result = calMulti(circleNum, minCommonMultiple);
        int left = n % circleSize;
        return (result % mod + findNBig(left, a, b) % mod) % mod;
    }

    /**
     * 求 a 和 b 的最小公倍数
     * 因为 a 和 b 最大40000，所以因数最大200
     */
    private int calMinCommonMultiple(int a, int b) {
        int minCommonMultiple = 1;
        for (int i = 2; i <= 200; ++i) {
            while (a % i == 0 && b % i == 0) {
                a /= i;
                b /= i;
                minCommonMultiple *= i;
            }
        }
        return minCommonMultiple * a * b;
    }

    private int calCircleSize(int minCommonMultiple, int a, int b) {
        int result = minCommonMultiple/a + minCommonMultiple/b - 1;
        // 如果最小公倍数是 a 或 b 其中的一个，那么循环的大小要-1
        // 不是这样吗？
//        if (minCommonMultiple == a || minCommonMultiple == b) {
//            result -= 1;
//        }
        return result;
    }

    /**
     * 在a的倍数和b的倍数中寻找第 idx 个大的数字
     */
    private int findNBig(int idx, int a, int b) {
        if (idx == 0) {
            return 0;
        }
        // 异或运算交换两数位置，让a成为小的数字
        if (a > b) {
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
        }
        int curIdx = 1;
        int result = a;
        int sumA = a, sumB = 0;
        while (curIdx < idx) {
            if (sumA + a < sumB + b) {
                sumA += a;
                result = sumA;
            } else {
                sumB += b;
                result = sumB;
            }
            ++curIdx;
        }
        return result;
    }

    /**
     * 计算 (bigNum * x) % mod 的结果，bigNum是一个很大的数字最大10^9
     * 每个中间结果都要 %mod，所以循环bigNum次再每次%mod不现实肯定超时
     */
    public int calMulti(int n, int x) {
        int result = 0;
        int flag = 0x40000000; // 对应32位二进制 0100 0000 0000 0000 0000 0000 0000 0000，或者表示为 (1 << 30) 也可
        while (flag != 0) {
            result = (result % mod + result % mod) % mod;
            if ((flag & n) == flag) {
                result = (result % mod + x % mod) % mod;
            }
            flag >>= 1;
        }
        return result;
    }

    @Test
    public void test01() {
        int n, a, b;

        n = 1;
        a = 2;
        b = 3;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 4;
        a = 2;
        b = 3;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 5;
        a = 2;
        b = 4;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 8;
        a = 10;
        b = 5;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 1000000000;
        a = 39999;
        b = 40000;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 307673195;
        a = 37340;
        b = 36427;
        System.out.println(nthMagicalNumber(n, a, b));
    }
}
